//==============================================================================
//
//  DIntArray - the one dimensional array of integers class in the ofc-library
//
//               Copyright (C) 2003  Dick van Oudheusden
//  
// This library is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public
// License as published by the Free Software Foundation; either
// version 2 of the License, or (at your option) any later version.
//
// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
// General Public License for more details.
//
// You should have received a copy of the GNU General Public
// License along with this library; if not, write to the Free
// Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
//
//==============================================================================
// 
//  $Date: 2008-08-02 05:58:14 $ $Revision: 1.8 $
//
//==============================================================================

#include "ofc/DIntArray.h"

#include <stdlib.h>
#include <limits.h>
#include <math.h>
#include <ctype.h>
#include <string.h>


#if _INTERFACE_

#include "ofc/config.h"

#include "ofc/DTextable.h"
#include "ofc/DComparable.h"
#include "ofc/DSizeable.h"
#include "ofc/DParsable.h"

#include "ofc/DText.h"

//
// The DIntArray class implements an one dimensional array of integers. It is of 
// course possible to create an array of integers with the classes DArray and DInt, 
// but this is not very efficient and a little bit clumsy. This class also implements some
// statistical methods.
// 
// @example
// #include <stdio.h>
// #include "ofc/DIntArray.h"
// 
// int main(int argc, char *argv[])
// {
//   DIntArray *arr1  = [DIntArray alloc];
//   DIntArray *arr2  = [DIntArray new  ];
//   DText     *str;
// 
//   int       int1[] = {9, 4, 2, 9, 3, 7};
//   int       int2[] = {3, 2, 1};
// 
//   [arr1 init :int1 :sizeof(int1)/sizeof(int)];  // Init with an array of integers
// 
//   printf("Length of array1:%ld.\n", [arr1 length]);
// 
//   str = [arr1 toText];                 // Convert the array to a string
//   printf("Array1 as string:%s.\n", [str cstring]);
//   [str free];
// 
//   [arr1 put :3 :8];                    // Change value on index 3 from 9 to 8
// 
//   [arr1 insert :2 :2 :int2 :sizeof(int2)/sizeof(int)]; // Replace value on index 2 with the int2 array
// 
//   [arr1 delete :4 :5];                 // Delete two values from the array
// 
//   str = [arr1 toText];
//   printf("Array1 as string:%s.\n", [str cstring]); // Print the modified string
//   [str free];
// 
//                                        // Searching in the array
//   printf("Value 3 is present %ld times in array1.\n", [arr1 count :3 :0 :-1]); // Count the occurences of an integer
// 
//   printf("First index of value 3:%ld.\n", [arr1 index :3 :0 :-1]);  // Find first index
// 
//                                        // Statistical methods
//   printf("Sum of array1:%ld\n",  [arr1 sum :0 :-1]);
//   printf("Max of array1:%d\n",   [arr1 max :0 :-1]);
//   printf("Min of array1:%d\n",   [arr1 min :0 :-1]);
//   printf("Avg of array1:%.1f\n", [arr1 average :0 :-1]);
//   printf("Std of array1:%.1f\n", [arr1 standardDeviation :0 :-1]);
//   
//   [arr1 sort :0 :-1];                  // Sort the array
// 
//   str = [arr1 toText];
//   printf("Array1 sorted as string:%s.\n", [str cstring]);
//   [str free];
// 
//                                        // Use array2 as lifo/fifo buffer
//   [arr2 size :50];                     // Insure the size of the buffer
// 
//   [arr2 push :1];
//   [arr2 push :2];
//   [arr2 push :3];
// 
//   printf("Length of lifo:%ld.\n", [arr2 length]);
//   printf("Top of lifo:%d.\n", [arr2 tos]);
//   printf("Pop value (%d) and another (%d).\n", [arr2 pop], [arr2 pop]);
// 
//   [arr2 clear];
// 
//   [arr2 enqueue :4];
//   [arr2 enqueue :5];
//   [arr2 enqueue :6];
//   [arr2 enqueue :7];
// 
//   printf("Length of fifo:%ld.\n", [arr2 length]);
//   printf("Dequeue value (%d) and another (%d).\n", [arr2 dequeue], [arr2 dequeue]);
// 
//                                        // Compare arrays
//   if ([arr1 compare :arr2] == 0)
//     printf("Array1 is equal to array2.\n");
//   else if ([arr1 compare :arr2] < 0)
//     printf("Array1 is smaller than array2.\n");
//   else 
//     printf("Array1 is greater than array2.\n");
// 
//   [arr1 free];                         // Cleanup
//   [arr2 free];
//     
//   return 0;
// }
// 

@interface DIntArray : Object <DTextable,DComparable,DSizeable,DParsable>
{
@private
  unsigned long  _size;     // the allocated size for the data
  unsigned       _extra;    // the extra size amount
  unsigned long  _length;   // the length of the data
  int           *_array;    // the array of integers
}

#endif



@implementation DIntArray


#if _PRIVATE_

//
// Convert the index to an array offset
// 
// @param array    the array
// @param index    the index in the array (-_length .. _length)
// 
// @return the offset in the array (0.._length)
// 
static long index2offset(DIntArray *array, int index)
{
  if (index < 0)
    index = array->_length + index;

  if (index < 0)
  {
    index  = 0;

    WARNING(DW_INVALID_ARG, "index");
  }
  if (index > array->_length)
  {  
    index = array->_length-1;

    WARNING(DW_INVALID_ARG, "index");
  }

  return index;
}
#endif


//// Constructors

//
// Initialise to an empty array
//
// @return the object
//

- (DIntArray *) init
{
  [super init];
  
  _length = 0;
  _size   = 0;
  _extra  = 0;
  _array  = NULL;
    
  return self;
}

//
// Initialise the object with integers
//
// @param ints     the integers
// @param length   the length of the integers
//
// @return the string object
//

- (DIntArray *) init :(const int *) ints :(unsigned long) length
{
  [self init];

  [self set :ints :length];
  
  return self;
}


//// Copy related methods

//
// Do a shallow copy of the array
//
// @return the object
//
- shallowCopy
{
  DIntArray *copy = [super shallowCopy];
  
  copy->_array = (int *) objc_malloc(sizeof(int) * _size);
  
  memcpy(copy->_array, _array, sizeof(int) * _length);
  
  return copy;
}


//// Deconstructor

//
// Free the object
//
// @return the object
//

- free
{
  if (_array != NULL)
  {
    objc_free(_array);
  }

  return [super free];
}


//// Member methods

//
// Check if the array is empty
//
// @return Is it empty ?
//

- (BOOL) isEmpty
{
  return (_length == 0);
}

//
// Return the length of the array
//
// @return the length
//

- (unsigned long) length
{
  return _length;
}

//
// Return the pointer to the array of integers
//
// @return the pointer to the array
//

- (const int *) array
{
  return _array;
}


//// Size methods

//
// Insure the size for the array
//
// @param size     the requested size (in elements) for the array
//
// @return the object
//

- (DIntArray *) size :(unsigned long) size
{
  if (size  > _size)
  {
    _size = size + _extra;
    
    if (_array == NULL)
    {
      _array = (int *) objc_malloc(sizeof(int) * _size);
    }
    else
    {
      _array = (int *) objc_realloc(_array, sizeof(int) * _size);
    }
  }

  return self;
}

//
// Set the amount of extra size increase if the size must be extended
//
// @param extra    the amount (def. 0)
//
// @return the object
//

- (DIntArray *) extra :(unsigned) extra
{
  _extra = extra;

  return self;
}


//// DTextable protocol methods

//
// Convert the object to a text string 
// 
// @return a (new) text string object
//
- (DText *) toText
{
  DText *text = [DText new];
  
  unsigned long index = 0;
  
  if (_length > 0)
  {
    DText *temp = [DText new];
    
    while (index < (_length-1))
    {
      [temp format :"%d",_array[index++]];
    
      [text append :[temp cstring]];
      [text push   :','];
    }
    
    [temp format :"%d", _array[index]];
    [text append :[temp cstring]];
    
    [temp free];
  }
  
  return text;
}


//// DParsable protocol methods

//
// Parse a string for an array of integers: <int>,<int>;<int>
// 
// @param cstr     the string to be parsed (moved to the first non-parsable character)
// 
// @return the result (0, ERANGE, ENODATA)
//
- (int) fromString :(char **) cstr
{
  int   result = 0;
  char *src    = *cstr;
  char *end    = src;
  char *last   = src;
  int   number;
  BOOL  done   = NO;
  
  [self clear];
  
  while (!done)
  {
    last = src;
    
    number = strtol(src, &src, 0);
    
    if (last == src)
    {
      done = YES;
    }
    else if ((number <= INT_MIN) || (number >= INT_MAX))
    {
      result = ERANGE;
      done   = YES;
    }
    else
    {
      [self size :_length+1];
      
      _array[_length++] = number;
      
      while (isspace(*src))
      {
        src++;
      }
      end = src;

      if ((*src == ',') || (*src == ';'))
      {
        src++;
      }
      else
      {
        done = YES;
      }
    }
  }
  
  if (end == *cstr)
  {
    result = ENODATA;
  }
  else
  {
    *cstr = end;
  }
  
  return result;
}

//// Array setters

//
// Clear the array
// 
// @return the object
// 

- (DIntArray *) clear
{
  _length = 0;
  
  return self;
}

//
// Set an array of integers in the object
//
// @param ints     the integers
// @param length   the length of the integers
//
// @return the object
//

- (DIntArray *) set :(const int *) ints :(unsigned long) length
{
  _length = 0;

  if (ints != NULL)
  {
    _length = length;
  }

  [self size :_length];

  memcpy(_array, ints, sizeof(int) * _length);
  
  return self;
}


//// Element methods

//
// Put an integer at the given index
//
// @param index     the index (-length..+length)
// @param element   the integer to be placed
//
// @return the object
//

- (DIntArray *) put :(long) index :(int) element
{
  if (_length > 0)
  {
    index = index2offset(self, index);

    _array[index] = element;
  }
  
  return self;
}

//
// Get the integer at the given index
//
// @param index    the index 
//
// @return the integer from the array
//

- (int) get :(long) index
{
  if (_length > 0)
  {
    index = index2offset(self, index);
  
    return _array[index];
  }
  else
    return 0;
}

// 
// Insert an integer at the given index
// 
// @param index    the index
// @param value    the value to be inserted
// 
// @return the object
//
- (DIntArray *) insert :(long) index :(int) value
{
  [self size :_length+1];
  
  index = index2offset(self, index);
  
  memmove(_array+index+1, _array+index, sizeof(int) * (_length-index));
  
  _array[index] = value;
  
  _length++;
  
  return self;
}
    
//
// Delete the integer at the given index
//
// @param index    the index
//
// @return the object
//

- (DIntArray *) delete :(long) index
{
  index = index2offset(self, index);
  
  if (_length > 0)
  {
    memmove(_array+index, _array+index+1, sizeof(int) * (_length-index-1));

    _length--;
  }
  
  return self;
}


//// Slice methods

//
// Insert an array of integers in a part of the array in the object
//
// @param from     the start index
// @param to       the end index (to >= (from-1))
// @param ints     the array with integers to be inserted
// @param length   the length of the integers
//
// @return the object
//

- (DIntArray *) insert :(long) from :(long) to :(const int *) ints :(unsigned long) length
{
  from = index2offset(self, from);
  to   = index2offset(self, to  );

  if (to >= (from-1))
  {
    length = (ints != NULL) ? length : 0;

    [self size :(_length+length-(to-from+1))];
    
    memmove(_array+from+length, _array+to+1, sizeof(int) * (_length-to-1));
    
    memmove(_array+from, ints, sizeof(int) * length);

    _length += (length-(to-from+1));
  }
    
  return self;
}

//
// Return a sub array
//
// @param from     the start index
// @param to       the end index (to >= from)
//
// @return a (new) integer array object
//

- (DIntArray *) get :(long) from :(long) to
{
  DIntArray *sub = [DIntArray new];
  
  from = index2offset(self, from);
  to   = index2offset(self, to  );

  if (to >= from)
  {
    [sub set :_array+from :(to - from + 1)];
  }
  
  return sub;
}

//
// Delete a range in the array
//
// @param from     the start index
// @param to       the end index (to >= from)
//
// @return the object
//

- (DIntArray *) delete :(long) from :(long) to
{
  if (_length > 0)
  {
    from = index2offset(self, from);
    to   = index2offset(self, to  );

    if (to > from)
    {
      memmove(_array+from, _array+to+1, sizeof(int) * (_length-to-1));

      _length -= (to-from+1);
    }
  }
  
  return self;
}


//// Array manipulation methods

//
// Append an array to the object
//
// @param ints     the integers to be appended
// @param length   the length of the integer array
//
// @return the object
//

- (DIntArray *) append :(const int *) ints :(unsigned long) length
{
  length = (ints != NULL) ? length : 0;

  if (length > 0)
  {
    [self size :(_length + length)];

    memcpy(_array + _length, ints, sizeof(int) * length);
    
    _length += length;
  }
  
  return self;
}

//
// Prepend an array in front of the object
//
// @param ints     the integers to be prepended
// @param length   the length of the integer array to be prepended
//
// @return the object
//

- (DIntArray *) prepend :(const int *) ints :(unsigned long) length
{
  length = (ints != NULL) ? length : 0;

  if (length > 0)
  {
    [self size :(_length + length)];

    memmove(_array + length, _array, sizeof(int) * _length);
    
    memcpy(_array, ints, sizeof(int) * length);

    _length += length;
  }

  return self;
}


//// Stack methods

//
// Push one integer at the end of the array
// 
// @param value    the integer that is placed at the end
//
// @return the object
//
- (DIntArray *) push :(int) value
{
  [self size :(_length + 1)];

  _array[_length++] = value;

  return self;
}

//
// Pop one integer from the end of the array
//
// @return the integer that is pulled (or 0 for empty stack)
//
- (int) pop
{
  int value = 0;
  
  if (_length > 0)
  {
    value = _array[--_length];
  }

  return value;
}

//
// Return the integer at the end of the array
// 
// @return the integer (or 0 for empty stack)
// 
- (int) tos
{
  if (_length > 0)
  {
    return _array[_length-1];
  }
  else
  {
    return 0;
  }
}

//// Queue methods (FIFO)

//
// Put an integer at the start of the array 
//
// @param value    the integer 
// 
// @return success
// 
- (BOOL) enqueue :(int) value
{
  [self size :(_length + 1)];

  memmove(_array + 1, _array, sizeof(int) * _length);
  
  _array[0] = value;
  
  _length++;
  
  return YES;
}

//
// Get the integer at the end of the array
// 
// @return the integer (or 0 for empty queue)
// 
- (int) dequeue
{
  int value = 0;
  
  if (_length > 0)
  {
    value = _array[--_length];
  }

  return value;
}


//// Comparable protocol methods

//
// Compare the integer array object with another integer array object
//
// @param other    the object that should be compared (!= nil)
//
// @return the compare result (-1, 0, 1)
//

- (int) compare :(DIntArray *) other
{
  if (other != nil)
  {
    int *i1                 = _array;
    const int *i2           = [other array];
    long l1                 = _length;
    long l2                 = [other length];
  
    while ((l1 > 0) && (l2 > 0) && (*i1 == *i2))
    {
      i1++; i2++; l1--; l2--;
    }
  
    if ((l1 > 0) && (l2 > 0))
    {
      return (*i1 > *i2) ? 1 : -1;
    }
    else if (l1 > 0)
    {
      return 1;
    }
    else if (l2 > 0)
    {
      return -1;
    }
  }
  else
  {
    WARNING(DW_INVALID_ARG, "other");
  }
  
  return 0;
}


//// Comparison methods

//
// Compare the object with another array of integers
//
// @param ints     the array of integers
// @param length   the length of the array
//
// @return the compare result (-1, 0, 1)
//

- (int) bcompare :(const int *) ints :(unsigned long) length
{
  const int *i1           = _array;
  long l1                 = _length;
  const int *i2           = ints;
  long l2                 = (ints != NULL) ? length : 0;
  
  while ((l1 > 0) && (l2 > 0) && (*i1 == *i2))
  {
    i1++; i2++; l1--; l2--;
  }
  
  if ((l1 > 0) && (l2 > 0))
  {
    return (*i1 > *i2) ? 1 : -1;
  }
  else if (l1 > 0)
  {
    return 1;
  }
  else if (l2 > 0)
  {
    return -1;
  }
  
  return 0;
}


//// Statistical methods

//
// Count the number of occurrences of an integer in the array
//
// @param search   the value that should be counted
// @param from     the start index 
// @param to       the end index (to >= from)
//
// @return the number of occurrences
//
- (unsigned long) count :(int) search :(long) from :(long) to  
{
  unsigned long  cnt  = 0;
  int           *pntr;
  
  from = index2offset(self, from);
  to   = index2offset(self ,to);

  pntr = _array + from;
  
  while (from <= to)
  {
    if (search == *pntr)
    {
      cnt++;
    }
    
    pntr++;
    from++;
  }
      
  return cnt;
}

//
// Return the first index where the search integer is found
//
// @param search   the integer that should be searched
// @param from     the start index
// @param to       the end index (to >= from)
//
// @return the first index or -1 = not found
//
- (long) index :(int) search :(long) from :(long) to 
{
  int *pntr;
  
  from = index2offset(self, from);
  to   = index2offset(self, to  );
  
  pntr = _array + from;
    
  while (from <= to)
  {
    if (search == *pntr)
    {
      return from;
    }
    from++;
    pntr++;
  }

  return -1;
}

//
// Return the last index where the search integer is found
//
// @param search   the integer that should be searched
// @param from     the start index
// @param to       the end index (to >= from)
//
// @return the last index or -1 = not found
//
- (long) rindex :(int) search :(long) from :(long) to
{
  int *pntr;
  
  from = index2offset(self, from);
  to   = index2offset(self, to  );

  pntr = _array + to;
  
  while (to >= from)
  {
    if (search == *pntr)
    {
      return to;
    }
    to--;
    pntr--;
  }
  
  return -1;
}

//
// Calculate the sum in a range of the integer array
// 
// @param from     the start index
// @param to       the end index (to >= from)
// 
// @return the sum of the integers
// 
- (long) sum :(long) from :(long) to
{
  int    *pntr;
  long    sum = 0;
  
  from = index2offset(self, from);
  to   = index2offset(self, to  );
  
  pntr = _array + from;
    
  while (from <= to)
  {
    sum += *pntr;
    
    from++;
    pntr++;
  }

  return sum;
}

//
// Determine the maximum integer in a range of the integer array
//
// @param from     the start index
// @param to       the end index (to >= from)
// 
// @return the maximum integer
// 
- (int) max :(long) from :(long) to
{
  int    *pntr;
  int    max = INT_MIN;
  
  from = index2offset(self, from);
  to   = index2offset(self, to  );
  
  pntr = _array + from;
    
  while (from <= to)
  {
    if (*pntr > max)
    {
      max = *pntr;
    }
    
    from++;
    pntr++;
  }

  return max;
}

//
// Determine the minimum integer in a range of the integer array
//
// @param from     the start index
// @param to       the end index (to >= from)
// 
// @return the minimum integer
// 
- (int) min :(long) from :(long) to
{
  int    *pntr;
  int    min = INT_MAX;
  
  from = index2offset(self, from);
  to   = index2offset(self, to  );
  
  pntr = _array + from;
    
  while (from <= to)
  {
    if (*pntr < min)
    {
      min = *pntr;
    }
    
    from++;
    pntr++;
  }

  return min;
}

//
// Calculate the average in a range of the integer array
// 
// @param from     the start index
// @param to       the end index (to >= from)
//
// @return the average (or 0.0)
// 
- (double) average :(long) from :(long) to
{
  int    *pntr;
  double avg    = 0.0;
  long   length = 0;
  
  from = index2offset(self, from);
  to   = index2offset(self, to  );
  
  pntr = _array + from;
    
  while (from <= to)
  {
    avg += (double) *pntr;
    
    length++;
    from++;
    pntr++;
  }
  
  if (length > 0)
  {
    avg /= (double) length;
  }
  
  return avg;
}

// 
// Calculate the variance in a range of the integer array
// 
// @param from     the start index
// @param to       the end index (to >= from)
// 
// @return the variance
// 
- (double) variance :(long) from :(long) to
{
  double variance = 0.0;
  double avg      = 0.0;
  long   length   = 0;
  int    *pntr;
  long   walk;
  
  from = index2offset(self, from);
  to   = index2offset(self, to  );
  
  pntr = _array + from;
  
  walk = from;
  while (walk <= to)
  {
    avg += (double) *pntr;
    
    length++;
    walk++;
    pntr++;
  }
  
  if (length > 0)
  {
    avg /= (double) length;
    
    pntr = _array + from;
    
    walk = from;
    while (walk <= to)
    {
      double diff = ((double) *pntr - avg);
      
      variance += (diff * diff);
      
      walk++;
      pntr++;
    }
    
    variance /= (double) length;
  }
  
  return variance;
}

//
// Calculate the standard deviation in a range of the integer array
// 
// @param from     the start index
// @param to       the end index (to >= from)
// 
// @return the standard deviation
// 
- (double) standardDeviation :(long) from :(long) to
{
  double result = [self variance :from :to];
  
  if (result > 0.0)
  {
    result = sqrt(result);
  }
  
  return result;
}


#if _PRIVATE_

//
// Compare function for sort method
// 
// @param first    the pointer to the first element
// @param second   the pointer to the second element
// 
// @return the compare result -1,0,1)
// 
static int _compare(const void *c1, const void *c2)
{
  int i1 = * ((int *) c1);
  int i2 = * ((int *) c2);
  
  if (i1 > i2)
  {
    return 1;
  }
  else if (i1 < i2)
  {
    return -1;
  }
  else
  {
    return 0;
  }
}
#endif

//
// Sort a range in the the integer array
//
// @param from     the start index
// @param to       the end index (to > from)
// 
// @return the object
// 
- (DIntArray *) sort :(long) from :(long) to
{
  from = index2offset(self, from);
  to   = index2offset(self, to  );

  if (to > from)
  {
    qsort(_array + from, (to - from + 1), sizeof(int), _compare);
  }
  
  return self;
}

//
// Invert a range in the integer array
// 
// @param from     the start index
// @param to       the end index (to >= from)
// 
// @return the object
// 
- (DIntArray *) invert :(long) from :(long) to
{
  from  = index2offset(self, from);
  to    = index2offset(self, to  );
  
  while (to > from)
  {
    int tmp = _array[to];
    
    _array[to] = _array[from];
    
    _array[from] = tmp;
    
    to--;
    from++;
  }
  
  return self;
}

@end

/*===========================================================================*/

